"Find the 10001st prime.
"
;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;; 
(defun p7 ()
  (n-th-prime 10001))

" bruce force version"
(defun n-th-prime (n)
  (loop for i to (1- n)
        and a = 1 then (get-next-prime (1+ a))
        finally (return a)))

(defun get-next-prime (value &optional (prime-test 'primep-2))
  (if (funcall prime-test value)
	  value
	  (get-next-prime (1+ value))))

;;; takes about 47 seconds to get the 10001 prime
(defun simple-prime-test (n)
  (defun test-inner (seeds result)
	(cond ((equal result t) nil)
		  ((null seeds) t)
	      (t (test-inner (cdr seeds) (= (mod n (car seeds)) 0)))))
  (if (<= n 1)
	  nil
      (test-inner (range 2 (sqrt n)) nil)))

;;; duplicated in p10.lisp
;;; much fast than simple-prime-test
;;; takes about 1.3 seconds to get the 10001 prime
(defun primep-2 (n)
  (cond ((= n 1) nil)
		((< n 4) t)
		((zerop (mod n 2)) nil)
		((< n 9) t) ;;; already excluded 4,6,8
		((zerop (mod n 3)) nil)
		(t (do ((r (floor (sqrt n))) (f 5 (+ f 6)))
			   ((or (zerop (mod n f)) (zerop (mod n (+ f 2))) (> f r))
				(if (> f r)
				     t
					 nil))
			   ;(print f)
			   ))))
(defun range (start end)
  (loop for i from start to end collect i)) 

;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;
(defun prime-list (start end)
  (remove-if-not
	'simple-prime-test
	(range start end)))

(defun prime-list-n-th (n)
  (mapcar
	'n-th-prime
	(range 1 n)))

;(format t "~a~%" (prime-list 2 100))
;(format t "~a~%" (prime-list-n-th 9))
;(format t "~a~%" (n-th-prime 10001))
(format t "~a~%" (time (p7)))
